﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Intrinsics.Arm;
using System.Text;
using System.Threading.Tasks;

public class Solution45
{
    public int Jump2(int[] nums)//超时
    {int len=nums.Length;

        int[] times = new int[nums.Length];
       
        for (int i = 1; i < nums.Length; i++)
        {
            times[i]=int.MaxValue;

        }
        times[0] = 0;
        for (int i = 0; i < nums.Length; i++)
        {
  
           int range= nums[i];//范围
            for (int j = 1; j <= range; j++)
            {

                if(i+j < len)
                {
                    times[i + j] = Math.Min(times[i] + 1, times[i + j]);
                }

               
            }

            for (int t = 0;t < nums.Length; t++)
            {
                Console.Write(times[t]+",");

            }
            Console.WriteLine();
        }

      

        return times[len-1];

    }
    public int Jump(int[] nums)//超时
    {
        //每次选择跳一个最远的范围，这个范围里面的都可以作为下一次的起跳点

        int far = 1;
        int start = 0;
        int end = 1;
        int count = 0;
        while (end < nums.Length)
        {
            for (int i = start; i < end; i++)
            {

                far=Math.Max(far,i+ nums[i]);
            }
            //跳一次
            start = end;
            end = far+1;

            count++;


        }

        return count;
    
    }
    }

class Program45
{
    static void Main45(string[] args)
    {
        Solution45 solution = new Solution45();
        int[] nums = [2, 3, 1, 1, 4];
    int res=    solution.Jump(nums);
        Console.WriteLine(res);
    }
}
